package avlTree;




/**
 * Creared with IntelliJ IDEA.
 * Description:
 * User:yxd
 * Date:2022-07-05
 * Time:12:53
 */
public class AVLTree {
    static class TreeNode{
        //内部类，表示AVL树的每个节点

        //val值
        public int val;
        //左孩子的引用
        public TreeNode left;
        //右孩子的引用
        public TreeNode right;
        //父亲节点的引用
        public TreeNode parent;
        //平衡因子(每个节点都有）
        public int bf;
        public TreeNode(int val){
            this.val = val;
        }
    }

    //根节点
    public TreeNode root;
    public boolean insert(int val){
        TreeNode node = new TreeNode(val);
        if(root == null){
            //没有根节点，要插入的就是根节点
            root = node;
            return true;
        }
        //记录每个节点的父节点
        TreeNode parent = null;
        //要移动的代节点
        TreeNode cur = root;
        //根据val的值和root进行比较来确定应该插入节点的位置
        while (cur != null){
            if(cur.val > val){
                //大于证明此节点应在左子树
                parent = cur;
                cur = cur.left;
            }else if(cur.val < val){
                //大于证明此节点应在右子树
                parent = cur;
                cur = cur.right;
            }else {
                //不能有值一样的节点
                return false;
            }
        }
        //此时cur为空，需要找到对应的位置
        if(parent.val > val){
            parent.left = node;
        }else{
            parent.right = node;
        }
        //而此时就需要对树进行平衡因子的调整了，保证树是高度平衡的
        //再反着回去写
        node.parent = parent;
        cur = node;
        //当父亲节点一直存在的时候，就表示没有调到根节点就需要继续调整
        while(parent != null){
            if(cur == parent.right){
                //在右边右树高度加一，因此bf+1
                parent.bf++;
            }else{
                //再左边，左树高度加一，因此bf-1
                parent.bf--;
            }
            //在这里就要进行判断了，如果此时的父亲节点如果平衡因子为0了，那么就不需要再往上走了，因为上面的都是平衡的，
            // 当前的父亲节点的平衡因子为0了表示插入的这个元素只影响到了这一棵树，上面是没有影响的，因此是0的话就就结束了,而其他情况还是需要考虑的
            if(parent.bf == 0){
                break;
            }else if(parent.bf == -1 || parent.bf == 1){
                //此时父亲节点的平衡因子为1、-1
                //此时表示当前树平衡了，但是不表示整棵树都平衡了，因此还需要继续往上走
                cur = parent;
                parent = cur.parent;

            }else{
                //此时父亲节点的平衡因子为2、-2
                if(parent.bf == 2){
                    //此时右树高 需要降低右树的高度
                    if(cur.bf == 1){
                        //左单旋
                        rotateLeft(parent);
                    }else{
                        rotateRL(parent);
                    }
                }else{
                    //此时左树高，需要降低左树的高度
                    if(cur.bf == 1){
                        //左右双旋
                        rotateLR(parent);
                    }else{
                        //右单旋
                        rotateRight(parent);
                    }
                }
                break;
            }
        }

        return true;
    }


    private void rotateRight(TreeNode parent){
        //右单旋
        //此时parent的平衡因子为-2，cur的平衡因子为-1


        TreeNode cur = parent.left;
        //记录cur的右节点
        TreeNode curR = cur.right;

        parent.left = curR;
        cur.right = parent;
        //如果cur有右节点需要赋给parent的左节点，但是没有就不需要给了


        if(curR != null){

            curR.parent = parent;
        }
        //然后将cur的右孩子改变为parent

        //需要记录parent的根节点
        TreeNode pParent = parent.parent;
        parent.parent = cur;

        //检查当前是不是根节点，不是根节点需要看是左子树，还是右子树
        if(pParent != null){
            //改变之前的指向
            cur.parent = pParent;
            if(parent == pParent.right){
                pParent.right = cur;
            }else{
                pParent.left = cur;
            }
        }else{
            //此时parent就是root，因为没有根节点
            root = cur;
            root.parent = null;
        }

        //最后记得一定要修改平衡因子
        parent.bf = 0;
        cur.bf = 0;
    }

    private void rotateLeft(TreeNode parent){
        //左单旋
        //此时parent平衡因子为2，cur的平衡因子为1
        //需要记录父亲节点
        TreeNode pParent = parent.parent;

        TreeNode cur = parent.right;
        //记录cur的左节点
        TreeNode curL = cur.left;

        parent.right = curL;
        cur.left = parent;
        //判断左节点是不是空的，如果是空的就不需要管了，不是空的就需要将parent右节点指向它，并且它的父亲节点为parent
        if(curL != null){
            //改变指向

            curL.parent = parent;
        }
        //改变cur的指向

        parent.parent = cur;
        //判断如果pParent不为空，就表示parent不是root，就需要看其是左孩子还是右孩子
        if(pParent != null){
            cur.parent = pParent;
            if(parent == pParent.right){
                pParent.right = cur;

            }else{
                pParent.left = cur;
            }
        }else{
            //是根节点
            root = cur;
            root.parent = null;
        }
        cur.bf = 0;
        parent.bf = 0;
    }
    private void rotateLR(TreeNode parent){
        //左右双旋
        TreeNode cur = parent.left;
        TreeNode curR = cur.right;
        //此时就需要看curR的平衡因子，再决定最后其他节点的平衡因子
        int bf = curR.bf;
        //先调用左旋再右旋
        rotateLeft(cur);
        rotateRight(parent);
        //这里通过规律可以得到当curR的bf值不同的时候，其需要改变的bf值也是不同的，因此里就需要做出修改
        if(bf == -1){
            //当bf为-1时，其应修改的如下
            curR.bf = 0;
            cur.bf = 0;
            parent.bf = 1;
        }else if(bf == 1){
            //当bf为1时，其应修改的如下

            curR.bf = 0;
            cur.bf = -1;
            parent.bf = 0;
        }
        //另外当bf为0的时候就已经平衡了，就不需要改了，因为在两次旋转的时候就已经将其改为0了
    }

    private void rotateRL(TreeNode parent) {
        //右左双旋
        TreeNode cur = parent.right;
        TreeNode curL = cur.left;
        //此时就需要看curL的平衡因子了，再决定最后其他节点的平衡因子
        int bf = curL.bf;
        rotateRight(cur);
        rotateLeft(parent);
        //这里通过规律可以得到当curR的bf值不同的时候，其需要改变的bf值也是不同的，因此里就需要做出修改
        if(bf == -1){
            //当bf为-1时，其应修改的如下
            parent.bf = 0;
//            cur.bf = 1;
//            curL.bf = 0;
            cur.bf = 0;
            curL.bf = 1;
        }else if(bf == 1){
            //当bf为1时，其应修改的如下
            parent.bf = -1;
            curL.bf = 0;
            cur.bf = 0;
        }
        //另外当bf为0的时候就已经平衡了，就不需要改了，因为在两次旋转的时候就已经将其改为0了
    }
    //中序遍历，判断是不是搜索树
    public void inorder(TreeNode root){
        if(root == null) return;

        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
    //求高度
    public int height(TreeNode root){
        if(root == null)return 0;
        int leftH = height(root.left);
        int rightH = height(root.right);
        return leftH >= rightH ? leftH + 1 : rightH + 1;
    }
    //判断是不是平衡树
    public boolean isBalanced(TreeNode root){
        if(root == null)return true;
        int leftH = height(root.left);
        int rightH = height(root.right);

        //需要判断平衡因子和自己算出来的平衡因子是否相同，不相同就表示自己写错了平衡因子，或者树不平衡
        if(rightH - leftH != root.bf){
            System.out.println(root.val + "平衡因子有问题哦");
            return  false;
        }
        //看左右书高低是否符合条件，以及左右子树是否平衡
        return Math.abs(leftH - rightH) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

}
